#include <ltypes.h>
#include <lmacros.h>

#include <boost/assert.hpp>

LLIB_BEGIN

template <typename BVTree_t>
geom::BVTreeIter<BVTree_t>* geom::BVTreeIter<BVTree_t>::Create( BVTree_t& tree, TraversalType type )
{
    BVTreeIter<BVTree_t>* iter;
    switch (type) {
        case Preorder:  iter = new BVTreeIter_Preorder<BVTree_t>();   break;
        case Inorder:   iter = new BVTreeIter_Inorder<BVTree_t>();    break;
        case Postorder: iter = new BVTreeIter_Postorder<BVTree_t>();  break;
        case Hierarchy: BOOST_ASSERT(FALSE);                          break; // not implement
        case LeafOnly:  BOOST_ASSERT(FALSE);                          break; // not implement
        default:        BOOST_ASSERT(FALSE);                          break; // not implement
    }
    iter->_tree = &tree;
    iter->reset();  //Every thing is ready when iterator is newly created
    return iter;
}

template <typename BVTree_t>
typename BVTree_t::BVNode* geom::BVTreeIter_Preorder<BVTree_t>::Next()
{
    if(_stack.empty()) return NULL;

    BVNode* res = _stack.back();
    _stack.pop_back();

    BVNode* left = res->GetChildLeft();
    if(left != NULL) _stack.push_back(left);
    BVNode* right = res->GetChildRight();
    if(right != NULL) _stack.push_back(right);

    return res;
}

template <typename BVTree_t>
void geom::BVTreeIter_Preorder<BVTree_t>::reset()
{
    _stack.clear();
    BVNode* root = _tree->GetRoot();
    _stack.push_back(root);
}

template <typename BVTree_t>
typename BVTree_t::BVNode* geom::BVTreeIter_Inorder<BVTree_t>::Next()
{
    if(_stack.empty()) return NULL;

    BVNode* res = _stack.back();
    _stack.pop_back();

    BVNode* node = res->GetChildRight();
    while(node != NULL) {
        _stack.push_back(node);
        node = node->GetChildLeft();
    }

    return res;
}

template <typename BVTree_t>
void geom::BVTreeIter_Inorder<BVTree_t>::reset()
{
    _stack.clear();
    BVNode* node = _tree->GetRoot();
    while(node != NULL) {
        _stack.push_back(node);
        node = node->GetChildLeft();
    }
}

template <typename BVTree_t>
typename BVTree_t::BVNode* geom::BVTreeIter_Postorder<BVTree_t>::Next()
{
    if(_stack.empty()) return NULL;

    BVNode* res = NULL;
    BVNode *node, *right;
    while(res == NULL) {
        node = _stack.back();
        right = node->GetChildRight();
        if(right == NULL || right == _lastPop) {
            _stack.pop_back();
            res = node;
            _lastPop = node;
        } else {
            node = right;
            while(node != NULL) {
                _stack.push_back(node);
                node = node->GetChildLeft();
            }
        }
    }

    return res;
}

template <typename BVTree_t>
void geom::BVTreeIter_Postorder<BVTree_t>::reset()
{
    _stack.clear();
    _lastPop = NULL;
    BVNode* node = _tree->GetRoot();
    while(node != NULL) {
        _stack.push_back(node);
        node = node->GetChildLeft();
    }
}

LLIB_END
